class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 超市内物品数量
     * @param V int整型 小美能拿的物品的价值总和
     * @param ai int整型vector 表示每个物品的价值
     * @return int整型
     */
    int shopping(int n, int V, vector<int>& ai) {
        // write code here
        sort(ai.begin(), ai.end());
        //把问题抽象成每个物品价值为1，而体积为ai，总体积不超过V，求最大价值。
        //value
        vector<vector<int>>Mat;
        Mat.resize(ai.size());
        for (int i = 0; i < ai.size(); i++)
        {
            Mat[i].resize(V + 1);
        }
        //mat[i][j]为将第i个物品纳入考虑后，j体积下的最大值。
        //每一个j体积都要放第i个物品从0放到满，挑max。再和不放比较。
        //第一列体积为0只能是0
        for (int i = 0; i < ai.size(); i++)
        {//除非最小价值物品为0，否则上限为0时不可能有数量
            if (ai[0] == 0)
            {
                Mat[i][0] = 1;
            }
            else { Mat[i][0] = 0; }
        }
        //第一行只能考虑第一个物品
        for (int j = 1; j < V + 1; j++)
        {
            if (j >= ai[0])
            {
                Mat[0][j] = 1;
            }
            else { Mat[0][j] = 0; }
        }
        for (int i = 1; i < ai.size(); i++)
        {
            for (int j = 1; j < V + 1; j++)
            {
                //只考虑以前的物品
                Mat[i][j] = Mat[i - 1][j];
                if (ai[i] <= j)
                {//混合考虑比较Mat[i-1][j-ai[i]]+1
                    Mat[i][j] = max(max(Mat[i][j], 1), Mat[i - 1][j - ai[i]] + 1);
                }
            }
        }
        return *max_element(Mat[ai.size() - 1].begin(), Mat[ai.size() - 1].end());
    }
};